1. Field of the Invention
This invention relates generally to signal processing systems and, more particularly, to apparatus and methods for receiving and processing signals that share a common receiver frequency band at the same time, referred to as cochannel signals. Even two signals transmitted on slightly separated frequency bands may be "cochannel" signals as seen by a receiver operating to receive signals on a bandwidth that overlaps both of the signals. In a variety of signal processing applications, there is a need to recover information contained in such multiple, simultaneously received signals. In the context of this invention, the--word "recover" or "recovery" encompasses separation of the received signals, "copying" the signals (i.e., retrieving any information contained in them), and, in some applications, combining signals received over multiple paths from a single source. The "signals" may be electromagnetic signals transmitted in the atmosphere or in space, acoustic signals transmitted through liquids or solids, or other types of signals characterized by a time-varying parameter, such as the amplitude of a wave. In accordance with another aspect of the invention, signal processing includes transmission of cochannel signals.
In the environment of the present invention, signals are received by "sensors." A sensor is an appropriately selected transducer for converting energy contained in the signal to a more easily manipulated form, such as electrical energy. In a radio communications application, electromagnetic signals are received by antennas and converted to electrical signals for further processing. After separation of the signals, they may be forwarded separately to transducers of a different type, such as loudspeakers, for converting the separated electrical signals into audio signals. In some applications, the signal content may be of less importance than the directions from which the signals were received, and in other applications the received signals may not be amenable to conversion to audible form. Instead, each recovered signal may contain information in digital form, or may contain information that is best understood by displaying it on a chart or electronic display device. Regardless of the environment in which the present invention is employed, it is characterized by multiple signals received by sensors simultaneously at the same or overlapping frequencies, the need to separate, recover, identify or combine the signals and, optionally, some type of output transducer to put the recovered information in a more easily discernible form.
2. Description of Related Art
Separation and recovery of signals of different frequencies is a routine matter and is handled by appropriate filtering of the received signals. It is common knowledge that television and radio signals are transmitted on different frequency bands and that one may select a desired signal by tuning a receiver to a specific channel. Separation and recovery of multiple signals transmitted at different frequencies and received simultaneously may be effected by similar means, using multiple tuned receivers in parallel. A more difficult problem, and the one with which the present invention is concerned, is how to separate and copy signals from multiple sources when the transmitted signals are at the same or overlapping frequencies. A single sensor, such as an antenna, is unable to distinguish between two or more received signals at the same frequency. However, antenna array technology provides for the separation of signals received from different directions. Basically, and as is well understood by antenna designers, an antenna array can be electronically "steered" to transmit or receive signals to or from a desired direction. Moreover, the characteristics of the antenna array can be selectively modified to present "nulls" in the directions of signals other than that of the signal of interest. A further development in the processing of array signals was the addition of a control system to steer the array toward a signal of interest. This feature is called adaptive array processing and has been known for at least two to three decades. See, for example, a paper by B. Widrow, P. E. Mantey, L. J. Griffiths and B. B. Goode, "Adaptive Antenna Systems," Proceedings of the IEEE, vol. 55, no. 12, pp. 2143-2159, December 1967. The steering characteristics of the antenna can be rapidly switched to receive signals from multiple directions in a "time-sliced" manner. At one instant the antenna array is receiving a signal from one source and at the next instant, from a different source in a different direction, but information from the multiple sources is sampled rapidly enough to provide a complete record of all the received signals. It will be understood that, although steered antenna array technology was developed principally in the communications and radar fields, it is also applicable to the separation of acoustic and other types of signals.
In the communications field, signals take a variety of forms. Stated most generally, a communication signal typically includes a carrier signal at a selected frequency, on which is impressed or modulated an information signal. There are a large number of different modulation schemes, including amplitude modulation, in which the amplitude of the signal is varied in accordance with the value of an information signal, while the frequency stays constant, and frequency or phase modulation, in which the amplitude of the signal stays constant while its frequency or phase is varied to encode the information signal onto the carrier. Various forms of frequency and phase modulation are often referred to as constant modulus modulation methods, because the amplitude or modulus of the signal remains constant, at least in theory. In practice, the modulus is subject to distortion during transmission, and various devices, such as adaptive equalizers, are used to restore the constant-modulus characteristic of the signal at a receiver. The constant modulus algorithm was developed for this purpose and later applied to antenna arrays in a process called adaptive beam forming The following references are provided by way for further background on the constant modulus algorithm:
B. Agee, "The least-squares CMA: a new technique for rapid correction of constant modulus signals," Proc. ICASSP-86, pp. 953-956, Tokyo, Japan, April 1986.
R. Gooch, and J. Lundell, "The CM array, an adaptive beamformer for constant modulus signals," Proc. ICASSP-86, pp. 2523-2526, Tokyo, Japan, April 1986.
J. Lundell, and B. Widrow, "Applications of the constant modulus adaptive algorithm to constant and non-constant modulus signals," Proc. Twenty-Second Asilomar Conference on Signals, Systems, and Computers, pp. 432-436, Pacific Grove, Calif., November 1988.
B. G. Agee, "Blind separation and capture of communication signals using a multi-target constant modulus beamformer," Proc. 1989 IEEE Military Communications Conference, pp. 340-346, Boston, Mass., October 1989.
R. D. Hughes, E. H. Lawrence, and L. P. Withers, Jr., "A robust adaptive array for multiple narrowband sources," Proc. Twenty-Sixth Asilomar Conference on Signals, Systems, and Computers, pp. 35-39, Pacific Grove, Calif., November 1992.
J. J. Shynk and R. P. Gooch, "Convergence properties of the multistage CMA adaptive beamformer," Proc. Twenty-Seventh Asilomar Conference on Signals, Systems, and Computers, pp. 622-626, Pacific Grove, Calif., November 1993.
The constant modulus algorithm works satisfactorily only for constant modulus signals, such as frequency-modulated (FM) signals or various forms of phase-shift keying (PSK) in which the phase is discretely or continuously varied to represent an information signal, but not for amplitude-modulated (AM) signals or modulation schemes that employ a combination of amplitude and phase modulation. There is a significant class of modulation schemes used known as M-ary quadrature amplitude modulation (QAM), used for transmitting digital data, whereby the instantaneous phase and amplitude of the carrier signal represents a selected data state. For example, 16ary QAM has sixteen distinct phase-amplitude combinations. The "signal constellation" diagram for such a scheme has sixteen points arranged in a square matrix and lying on three separate constant-modulus circles. A signal constellation diagram is a convenient way of depicting all the possible signal states of a digitally modulated signal. In such a diagram, phase is represented by angular position and modulus is represented by distance from an origin.
The constant modulus algorithm has been applied with limited success to a 16-ary QAM scheme, because it can be represented as three separate constant-modulus signal constellations. However, for higher orders of QAM the constant modulus algorithm provides rapidly decreasing accuracy. For suppressed-carrier AM, the constant modulus approach fails completely in trying to recover cochannel AM signals. If there are multiple signals, the constant modulus algorithm yields signals with "cross-talk," i.e. with information in the two signals being confused. For a single AM signal in the presence of noise, the constant-modulus algorithm yields a relatively noisy signal.
Because antenna arrays can be steered electronically to determine the directions of signal sources, it was perhaps not surprising that one well known form signal separator available prior to the present invention used direction finding as its basis. The approach is referred to as DF-aided copy, where DF means direction finding. This is an open-loop technique in which steering vectors that correspond to estimated signal source bearings are first determined; then used to extract waveforms of received signals. However, the direction finding phase of this approach requires a knowledge of the geometry and performance characteristics of the antenna array. Then steering vectors are fed forward to a beamformer, which nulls out the unwanted signals and steers one or more antenna beam(s) toward each selected source.
Prior to the present invention, some systems for cochannel signal separation used direction-finding (DF)-beamforming. Such systems separate cochannel signals by means of a multi-source (or cochannel) super-resolution direction finding algorithm that determines steering vectors and directions of arrival (DOAs) of multiple simultaneously detected cochannel signal sources. An algorithm determines beam-forming weight vectors from the set of steering vectors of the detected signals. The beamforming weight vectors are then used to recover the signals. Any of several well-known multi-source super-resolution DF algorithms can be used in such a system. Some of the better known ones are usually referred to by the acronyms MUSIC MUltiple SIgnal Classification), ESPRIT (Estimation of Signal Parameters via Rotational Invariance Techniques), Weighted Subspace Fitting (WSF), and Method of Direction Estimation (MODE).
MUSIC was developed in 1979 simultaneously by Ralph Schmidt in the United States and by Georges Bienvenu and Lawrence Kopp in France. The Schmidt work is described in R. O. Schmidt, "Multiple emitter location and signal parameter estimation," Proc. RADC Spectrum Estimation Workshop, pp. 243-258, Rome Air Development Center, Griffiss Air Force Base, NY, Oct. 3-5, 1979. The Bienvenu work is described in G. Bienvenu and L. Kopp, "Principle de la goniometrie passive adaptative," Proc. Colloque GRETSI, pp. 106/1-106/10, Nice, France, May 1979. MUSIC has been extensively studied and is the standard against which other super-resolution DF algorithms are compared.
ESPRIT is described in many publications in the engineering signal processing literature and is the subject of U.S. Pat. No. 4,750,147 entitled "Method for estimating signal source locations and signal parameters using an array of sensor pairs," issued to R. H. Roy III et al. ESPRIT was developed by Richard Roy, III, Arogyaswami Paulraj, and Prof. Thomas Kailath at Stanford University. It was presented as a super-resolution algorithm for direction finding in the following series of publications starting in 1986:
A. Paulraj, R. Roy, and T. Kailath, "A subspace rotation approach to signal parameter estimation," Proc. IEEE, vol. 74, no. 4, pp. 1044-1045, July 1986.
R. Roy, A. Paulraj, and T. Kailath, "ESPRIT--A subspace rotation approach to estimation of parameters of cisoids in noise," IEEE Trans. Acoust., Speech, and Signal Processing, vol. ASSP-34, no. 5, pp. 1340-1342, October 1986.
R. H. Roy, ESPRIT--Estimation of Signal Parameters via Rotational Invariance Techniques, doctoral dissertation, Stanford University, Stanford, Calif., 1987.
R. Roy and T. Kailath, "ESPRIT--Estimation of signal parameters via rotational invariance techniques," IEEE Trans. Acoust., Speech, and Signal Processing, vol. ASSP-37, no. 7, pp. 984-995, July 1989.
B. Ottersten, R. Roy, and T. Kailath, "Signal waveform estimation in sensor array processing," Proc. Twenty-Third Asilomar Conference on Signals, Systems, and Computers, pp. 787-791, Pacific Grove, Calif., November 1989.
R. Roy and T. Kailath, "ESPRIT--Estimation of signal parameters via rotational invariance techniques," Optical Engineering, vol. 29, no. 4, pp. 296-313, April 1990.
MUSIC and ESPRIT both require the same "narrowband array assumption," which is further discussed below in the detailed description of the invention, and both are modulation independent, a feature shared by all cochannel signal separation and recovery techniques that are based on the DF-beamforming method.
ESPRIT calculates two N-by-N covariance matrices, where N is the number of antenna elements, and solves a generalized eigenvalue problem numerically (instead of using a calibration table search, as MUSIC does). It does this for every block of input samples. MUSIC calculates a single N-by-N covariance matrix, performs an eigendecomposition, and searches a calibration table on every block of input array samples (snapshots).
MUSIC and ESPRIT have a number of shortcomings, some of which are discussed in the following paragraphs.
ESPRIT was successfully marketed based on a single, key advantage over MUSIC. Unlike MUSIC, ESPRIT did not require array calibration. In ESPRIT, the array calibration requirement was eliminated, and a different requirement on the antenna array was substituted. The new requirement was that the array must have a certain geometrical property. Specifically the array must consist of two identical sub-arrays, one of which is offset from the other by a known displacement vector. In addition, ESPRIT makes the assumption that the phases of received signals at one sub-array are related to the phases at the other sub-array in an ideal theoretical way.
Another significant disadvantage of ESPRIT is that, although it purports not to use array calibration, it has an array manifold assumption hidden in the theoretical phase relation between sub-arrays. "Array manifold" is a term used in antenna design to refer to a multiplicity of physical antenna parameters that, broadly speaking, define the performance characteristics of the array.
A well known difficulty with communication systems, especially in an urban environment, is that signals from a single source may be received over multiple paths that include reflections from buildings and other objects. The multiple paths may interpose different time delays, phase changes and amplitude changes on the transmitted signals, rendering reception more difficult, and transmission uncertain. This difficulty is referred to as the multipath problem. It is one that has not been adequately addressed by signal processing systems of the prior art.
Neither MUSIC nor ESPRIT can operate in a coherent multipath environment without major added complexity. A related problem is that, in a signal environment devoid of coherent multipath, no DF-beamforming method can separate signals from sources that are collinear with the receiving array, i.e. signal sources that are in line with the array and have zero angular separation. Even in a coherent multipath environment, DF-beamforming methods like MUSIC and ESPRIT cannot separate and recover cochannel signals from collinear sources.
Another difficulty with ESPRIT is that it requires two antenna sub-arrays and is highly sensitive to mechanical positioning of the two sub-arrays, and to the electromagnetic matching of each antenna in one sub-array with its counterpart in the other sub-array. Also ESPRIT requires a 2N-channel receiver, where N is the number of antenna elements, and is highly sensitive to channel matching.
Another significant drawback in both MUSIC and ESPRIT is that they fail abruptly when the number of signals detected exceeds the capacity, N, equal to the number of antennas in the case of MUSIC, or half the number of antennas in the case of ESPRIT.
A fundamental problem with both MUSIC and ESPRIT is that they use open-loop feed-forward computations, in which errors in the determined steering vectors are uncorrected, uncorrectable, and propagate into subsequent calculations. As a consequence of the resultant inaccurate steering vectors, MUSIC and ESPRIT have poorcross-talk rejection, as measured by signal-to-interference-plus-noise ratio (SINR) at the signal recovery output ports.
ESPRIT is best suited to ground based systems where its antenna requirements are best met and significant computational resources are available. MUSIC has simpler antenna array requirements and lends itself to a wider range of platforms, but also needs significant computational resources.
Another limitation of most signal recovery systems of the prior art is that they rely on first-order and second-order statistical moments of the received signal data. A moment is simply a statistical quantity derived from the original data by mathematical processing at some level. An average or mean value of the several signals received at a given time is an example of a first-order moment. The average of the squares of the signal values (proportional to signal powers) is an example of a second-order moment. Even if one considers just one signal and a noise component, computing the average of the sum of the squares produces a cross-term involving the product of signal and noise components. Typically, engineers have managed to find a way to ignore the cross-term by assuming that the signal and the noise components are statistically independent. At a third-order level of statistics, one has to assume that the signal and noise components have zero mean values in order to eliminate the cross-terms in the third-order moment. For the fourth-order and above, the computations become very complex and are not easily simplified by assumptions. In most prior art signal analysis systems, engineers have made the gross assumption that the nature of all signals is Gaussian and that there is no useful information in the higher-order moments. Higher-order statistics have been long recognized in other fields and there is recent literature suggesting their usefulness in signal recovery. Prior to this invention, cumulant-based solutions have been proposed to address the "blind" signal separation problem, i.e. the challenge to recover cochannel signals without knowledge of antenna array geometry or calibration data. See, for example, the following references:
J.-F. Cardoso, "Source separation using higher order moments," Proc. ICASSP-89, pp. 2109-2112, Glasgow, Scotland, May 1989.
J.-F. Cardoso, "Eigen-structure of the fourth-order cumulant tensor with application to the blind source separation problem," Proc. ICASSP-90, pp. 2655-2658, Albuquerque, N. Mex., April 1990.
J.-F. Cardoso, "Super-symmetric decomposition of the fourth-order cumulant tensor: blind identification of more sources than sensors," Proc. ICASSP-91, pp. 3109-3112, Toronto, Canada, May 1991.
J.-F. Cardoso, "Higher-order narrowband array processing," International Signal Processing Workshop on Higher Order Statistics, pp. 121-130, Chamrousse-France, Jul. 10-12, 1991.
J.-F. Cardoso, "Blind beamforming for non-Gaussian sources," IEE Proceedings Part F, vol. 140, no. 6, pp. 362-370, December 1993.
P. Comon, "Separation of stochastic processes," Proc. Vail Workshop on Higher-Order Spectral Analysis, pp. 174-179, Vail, Color., USA, June 1989.
P. Comon, "Independent component analysis," Proc. of Intl. Workshop on Higher-Order Statistics, pp. 111-120, Chamrousse, France, 1991.
P. Comon, C. Jutten, and J. Herault, "Blind separation of sources, part II: problems statement," Signal Processing, vol. 24, no. 1, pp. 11-20, July 1991.
E. Chaumette, P. Comon, and D. Muller, "ICA-based technique for radiating sources estimation: application to airport surveillance," IEE Proceedings Part F, vol. 140, no. 6, pp. 395-401, December 1993.
Z. Ding, "A new algorithm for automatic beamforming," Proc. Twenty-Fifth Asilomar Conference on Signals, Systems, and Computers, pp. 689-693, Pacific Grove, Calif., November 1991.
M. Gaeta and J.-L. Lacoume, "Source separation without a-priori knowledge: the maximum likelihood solution," Proc. EUSIPCO, pp. 621-624, 1990.
E. Moreau, and O. Macchi, "New self-adaptive algorithms for source separation based on contrast functions," Proc. IEEE SP Workshop on Higher-Order Statistics, pp. 215-219, Lake Tahoe, USA, June 1993.
P. Ruiz, and J. L. Lacoume, "Extraction of independent sources from correlated inputs: a solution based on cumulants," Proc. Vail Workshop on Higher-Order Spectral Analysis, pp. 146-151, Vail, Colo., USA, June 1989.
E. H. Satorius, J. J. Mulligan, Norman E. Lay, "New criteria for blind adaptive arrays," Proc. Twenty-Seventh Asilomar Conference on Signals, Systems, and Computers, pp. 633-637, Pacific Grove, Calif., November 1993.
L. Tong, R. Liu, V. Soon, and Y. Huang, "Indeterminacy and identifiability of blind identification," IEEE Trans. Circuits and Systems, vol. 38, pp. 499-509, May 1991.
L. Tong, Y. Inouye and R. Liu, "Waveform preserving blind estimation of multiple independent sources," IEEE Trans. Signal Processing, vol. 41, no. 7, pp. 2461-2470, July 1993.
However, all of these approaches to blind signal recovery address the static case in which a batch of data is given to a processor, which then determines the steering vectors and exact waveforms. These prior approaches do not have the ability to identify new sources that appear or existing sources that are turned off. In addition, previously proposed algorithms require multiple levels of eigendecomposition of array covariance and cumulant matrices. Their convergence to reliable solutions depends on the initialization and utilization of the cumulant matrices that can be derived from array measurements. Furthermore, previous cumulant-based algorithms have convergence problems in the case of identically modulated sources in general.
Ideally, a system for receiving and processing multiple cochannel signals should make use of statistics of the measurements, and should not need to rely on knowledge of the geometry or array manifold of the sensors, i.e., the array calibration data. Also, the system should be able to receive and process cochannel signals regardless of their modulation or signal type, e.g. it should not be limited to constant-modulus signals. More generally, the ideal cochannel signal processing system should not be limited to any modulation properties, such as baud rate or exact center frequency. Any system that is limited by these properties has only a limited range of source types that can be separated, and is more suitable for interference suppression in situations where the desired signal properties are well known. Another desirable property of the ideal cochannel signal receiving and processing system is that it should operate in a dynamic way, identifying new signal sources that appear and identifying sources that disappear. Another desirable characteristic is a very high speed of operation allowing received signals to be processed in real time. As will shortly become apparent, the present invention meets and exceeds these ideal characteristics for cochannel signal processing.